Three-dimensional (“3D”) digital data may be produced by a variety of devices that involve three-dimensional scanning or sampling and/or numerical modeling. For example, computed tomography (CT) and magnetic resonance (MR) devices scan portions of the human body and generate image slices of the body, which when combined or stacked, generate a 3D representation of the body, including its surface and internal volume. Laser scanners also generate 3D digital data. A long range laser scanner is fixed in one location and rotated to scan objects around it. Alternatively, a short range laser scanner is mounted on a device that moves around an object while scanning it. In either case, the location of each point scanned is represented as a polar coordinate since the angle between the scanner and the object and distance from the scanner to the object are known. The polar coordinates are then converted to 3D Cartesian coordinates and stored along with a corresponding intensity or color value for the data point collected by the scanner.
As described above, a 3D scanning/sampling/modeling device may generate 3D digital data by collecting a complete set of (x, y, z) locations that represent the shape of an object. Once collected, these point sets are sent to an image rendering system, which then processes the point data to generate a 3D image of the object. The term “point cloud” is used to describe point sets with a high magnitude of points. The data points are unorganized and spaced irregularly within the cloud. Although point cloud data can directly be used to generate 3D images, obtaining desired results from point cloud data is algorithmically non-trivial due to the lack of connectivity information between the points and computationally intensive due, in part, to the high magnitude of unorganized points being processed.
Alternatively, surface point cloud data can be transformed to polygons and the resultant 3D image of the surface of the corresponding object is generated from a mesh of polygons. While point cloud data may be transformed into polygon data, polygon-style rendering engines are still computationally intensive due to the large magnitude of polygons and cannot easily represent the internal volume of solid objects.
Volume graphics represent the most promising way to achieve the degree of realism required for high quality simulations and visualization applications because volume models can contain all the surface and internal characteristics of a real object. In the case of volume graphics, volume elements (i.e., “voxels”) are the base data used to represent 3D objects, rather than cloud points or polygons. Voxels are simply pixels that have a third coordinate z in addition to x and y coordinates in a Cartesian coordinate system. In other words, voxels are equally sized cubes that comprise a discretely defined 3D space. However, most archived 3D digital data is in point cloud format or polygon format. In addition, most 3D scanning/sampling/modeling devices generate point cloud or polygon data. Accordingly, there is a need for a method and apparatus, which converts point cloud data to volumetric data. More specifically, the method and apparatus should transform the unorganized, irregular data points of the point cloud into an organized regular three-dimensional array of voxels. Since point cloud data consists of floating point numbers (i.e., due to the fact points are not evenly spaced from one another in the cloud), the method and apparatus should transform the floating point numbers into integer based volume data. Further, the method and apparatus should also transfer any attribute data such as intensity or color from the cloud points to the corresponding voxel.